﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Data;
using System.Windows.Documents;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Media.Imaging;
using System.Windows.Navigation;
using System.Windows.Shapes;

namespace WpfAStar
{
    /// <summary>
    /// Interaction logic for MainWindow.xaml
    /// </summary>
    public partial class MainWindow : Window
    {
        enum WalkType
        {
            None,
            Open,
            Close,
        }
        enum BlockType
        {
            None,
            Star,
            End,
            Block
        }
        struct Pos : IEquatable<Pos>
        {
            public int X;
            public int Y;

            public bool Equals(Pos other) => X == other.X && Y == other.Y;

            public Vector2 ToV2() => new(X, Y);

        }
        class Grid
        {
            public Pos Pos;
            public bool Block => BlockType is BlockType.Block;
            public BlockType BlockType;
            public WalkType WalkType;
            public TextBlock Draw;
            public TextBlock DrawF;
            public Grid Parent;
            public bool Path = false;
            public float f;
            public (string, Color) TextColor()
            {
                if (BlockType == BlockType.Star)
                    return ("始", Color.FromRgb(0, byte.MaxValue, 0));
                if (BlockType == BlockType.End)
                    return ("终", Color.FromRgb(0, 0, byte.MaxValue));
                if (Path)
                    return ("路", Color.FromRgb(0, byte.MaxValue, byte.MaxValue));

                if (Block)
                    return ("阻", Color.FromRgb(byte.MaxValue, 0, 0));

                if (WalkType == WalkType.Open)
                    return ("开", Color.FromRgb(byte.MaxValue/2, byte.MaxValue / 2, 0));

                if (WalkType == WalkType.Close)
                    return ("闭", Color.FromRgb(byte.MaxValue/2, 0, byte.MaxValue/2));



                return (" ", Color.FromRgb(byte.MaxValue, 0, 0));
            }
        }
        Grid[,] map = new Grid[30, 20];

        Pos start;
        Pos end;

        public MainWindow()
        {
            InitializeComponent();
            canvas.Background = new SolidColorBrush(Color.FromRgb(0, 0, 0));
        }
        void drawText(Grid grid)
        {
            if (grid.Draw is null)
            {
                const int spaceDistance = 40;
                grid.Draw = new TextBlock();
                this.canvas.Children.Add(grid.Draw);
                Canvas.SetLeft(grid.Draw, grid.Pos.X * spaceDistance);
                Canvas.SetTop(grid.Draw, grid.Pos.Y * spaceDistance);

                grid.DrawF = new TextBlock();
                this.canvas.Children.Add(grid.DrawF);
                Canvas.SetLeft(grid.DrawF, grid.Pos.X * spaceDistance);
                Canvas.SetTop(grid.DrawF, grid.Pos.Y * spaceDistance + 15);
                grid.DrawF.Foreground = new SolidColorBrush(Color.FromRgb(byte.MaxValue / 2, byte.MaxValue / 2, byte.MaxValue / 2));
            }

            (grid.Draw.Text, var color) = grid.TextColor();
            grid.DrawF.Text = grid.f == 0 ? "" : grid.f.ToString("0.0");
            grid.Draw.Foreground = new SolidColorBrush(color);
        }
        private void Button_Click(object sender, RoutedEventArgs e)
        {
            foreach (var (x, y, grid) in RandomMap())
            {
                drawText(grid);
            }

        }
        private IEnumerable<(int, int, Grid)> RandomMap()
        {
            canvas.Children.Clear();
            start.X = Random.Shared.Next(map.GetLength(0));
            start.Y = Random.Shared.Next(map.GetLength(1));
            end.X = Random.Shared.Next(map.GetLength(0));
            end.Y = Random.Shared.Next(map.GetLength(1));

            for (int x = 0; x < map.GetLength(0); ++x)
            {
                for (int y = 0; y < map.GetLength(1); ++y)
                {
                    var grid = map[x, y] = new() { Pos = new() { X = x, Y = y } };
                    if (x == start.X && y == start.Y)
                        grid.BlockType = BlockType.Star;
                    else if (x == end.X && y == end.Y)
                        grid.BlockType = BlockType.End;
                    else
                        grid.BlockType = System.Random.Shared.Next(3) == 0 ? BlockType.Block : BlockType.None;

                    grid.WalkType = WalkType.None;
                    yield return (x, y, grid);
                }
            }

            curStep = AStar().GetEnumerator();
        }
        private IEnumerable<Grid> AStar()
        {
            var startGrid = map[start.X, start.Y];
            var endGrid = map[end.X, end.Y];
            List<Grid> listOpen = new();// Open list 里的格子都是下一步可以到达的（当然可能是退回某点后下一步到达），在最终最短路径中，open list中的格子可能会是沿途经过的，也有可能不经过。基本上 open list 是一个待检查的方格列表。
            List<Grid> listClose = new();

            void RemoveFromOpen(Grid grid)
            {
                grid.WalkType = WalkType.Close;
                listOpen.Remove(grid);
                listClose.Add(grid);
            }
            bool AddToOpen(int x, int y, Grid parent)
            {
                if (x < 0 || x >= map.GetLength(0))
                    return false;
                if (y < 0 || y >= map.GetLength(1))
                    return false;

                var grid = map[x, y];
                //如果不在CLOSE表中，就将它们放入OPEN表
                if (listClose.Contains(grid))
                    return false;
                if (listOpen.Contains(grid))
                    return false;
                if (grid.Block)
                    return false;
                grid.Parent = parent;
                grid.f = f(grid);
                grid.WalkType = WalkType.Open;
                listOpen.Add(grid);
                return true;
            }
            AddToOpen(startGrid.Pos.X, startGrid.Pos.Y, null);//首先将起始结点S放入OPEN表，CLOSE表置空
            yield return (startGrid);

            //同时计算每一个后继结点的估价值f(n)，将OPEN表按f(x)排序，最小的放在表头，重复算法，回到1
            float g(Grid grid)//它表示从起始搜索点到当前点的代价（通常用某结点在搜索树中的深度来表示）
            {
                int ret = 0;//每次计算，耗时较多
                for (var g = grid; g.Parent != null; g = g.Parent)
                {
                    ++ret;
                }
                return ret;
            }
            float h(Grid n) => Vector2.Distance(n.Pos.ToV2(), endGrid.Pos.ToV2());//h(n)，它表示启发式搜索中最为重要的一部分，即当前结点到目标结点的估值，h(n)设计的好坏，直接影响着具有此种启发式函数的启发式算法的是否能称为A*算法。
            float f(Grid grid) => g(grid) + h(grid);

            while (true)
            {
                if (listOpen.Count == 0)
                    yield break;
                if (listOpen.First().Pos.Equals(end)) //n是目标解吗？是，找到一个解（继续寻找，或终止算法）。
                    yield break;

                var openHead = listOpen.First();
                //将n的所有后继结点展开，就是从n可以直接关联的结点（子结点），
                //List<Grid> nextGrid = new();

                foreach (var (x, y) in new (int, int)[] { (1, 0), (-1, 0), (0, 1), (0, -1) })
                {
                    var posX = openHead.Pos.X + x;
                    var posY = openHead.Pos.Y + y;
                    if (AddToOpen(posX, posY, openHead))
                        yield return (map[posX, posY]);

                }
                RemoveFromOpen(openHead);
                yield return (openHead);
                listOpen.Sort((x, y) =>
                {

                    if (x.f > y.f) return 1;
                    if (x.f < y.f) return -1;
                    return 0;
                });
            }
        }

        IEnumerator<Grid> curStep;
        private void NextStep_Click(object sender, RoutedEventArgs e)
        {
            Stopwatch stopwatch = Stopwatch.StartNew();
            var ok = curStep.MoveNext();
            stopwatch.Stop();
            spanTime.Content = $"单步耗{stopwatch.Elapsed.TotalSeconds.ToString("0.00000000")}秒";
            if (ok)
            {
                stepResult.Content = "单步寻路成功";
                drawText(curStep.Current);
                return;
            }

            stepResult.Content = "单步寻路结束";
            DrawPath();
        }

        private void DrawPath()
        {
            var endGrid = map[end.X, end.Y];
            for (var path = endGrid; path != null; path = path.Parent)
            {
                path.Path = true;
                drawText(path);
            }
        }

        private void FindPath_Click(object sender, RoutedEventArgs e)
        {
            Stopwatch stopwatch = Stopwatch.StartNew();
            foreach(Grid grid in AStar())
            {

            }
            stopwatch.Stop();
            spanTime.Content = $"完整耗{stopwatch.Elapsed.TotalSeconds.ToString("0.00000000")}秒";
            stepResult.Content = "完整寻路结束";
            foreach(Grid grid in map)
                drawText(grid);

            DrawPath();
        }

        private void Grid_TouchEnter(object sender, TouchEventArgs e)
        {

        }

        private void Window_Initialized(object sender, EventArgs e)
        {
            
        }

        private void Window_Loaded(object sender, RoutedEventArgs e)
        {
            Button_Click(sender,e);
        }
    }
}
